package arithmetic.demo13;

/**
 * 贪心_正难则反+分类讨论 + 贪心: 可被3 整除的最大和
 */

class Solution {
    public int maxSumDivThree(int[] nums) {
        int len = nums.length;
        int INF = 0x3f3f3f3f;
        // 统计次小值和最小值
        int oneMin = INF, one2Min = INF, twoMin = INF, two2Min = INF;

        // 累加所有结果
        // 获取其中的 % 3 的数字的最小值和次小值
        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (num % 3 == 1) {
                // 取出 1 的最小和次小 
                if (num < oneMin) {
                    one2Min = oneMin;
                    oneMin = num;
                } else if (num >= oneMin && num <= one2Min) {
                    one2Min = num;
                }
            } else if (num % 3 == 2) {
                // 取出 2 的最小和次小 
                if (num < twoMin) {
                    two2Min = twoMin;
                    twoMin = num;
                } else if (num >= twoMin && num <= two2Min) {
                    two2Min = num;
                }
            }
        }

        // 对最终结果分类讨论
        if (sum % 3 == 0) {
            return sum;
        } else if (sum % 3 == 1) {
            // 1 % 3 = 1 或者 ( 2 + 2 ) % 3 = 1
            // 返回最大的差值
            return Math.max(sum - oneMin, sum - twoMin - two2Min);
        } else {
            // 2 % 3 = 1 或者 ( 1 + 1 ) % 3 = 2
            // 返回最大的差值
            return Math.max(sum - oneMin - one2Min, sum - twoMin);
        }

    }
}

/**
 * 动态规划_多状态dp + 拷贝 : 可被三整除的最大和
 */

class Solution1 {
    public int maxSumDivThree(int[] nums) {
        // 动态规划思想

        // 创建dp
        int[] dp = new int[3];
        int INF = -0x3f3f3f3f;
        dp[1] = INF;
        dp[2] = INF;

        // 填表
        for (int num : nums) {
            // 本身余数
            int r = num % 3;
            // 拷贝一份新的dp
            int[] newDp = dp.clone();

            // 开始状态转移
            for (int i = 0; i < 3; i++) {
                newDp[(i + r) % 3] = Math.max(newDp[(i + r) % 3], dp[i] + num);
            }
            // 重新赋值给原dp
            dp = newDp;
        }

        return dp[0];
    }
}

/**
 * 贪心_ 贪心 + 填格子:距离相等的条形码
 */

class Solution2 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        // 贪心 + 填格子
        int len = barcodes.length;
        // 使用哈希表来统计
        int[] hash = new int[10001];
        // 统计个数并找出最大数量
        int maxNum = 0, max = 0;
        for(int num : barcodes) {
            hash[num]++;
            if(hash[num] > max) {
                max = hash[num];
                maxNum = num;
            }
        }

        int[] ret = new int[len];
        // 先填入最大数量的数字
        int i = 0;
        while(hash[maxNum] != 0) {
            ret[i] = maxNum;
            i += 2;
            hash[maxNum]--;
        }


//        填入其他
        for(int k = 0; k < 10001; k++) {
            // 查找数据
            while(hash[k] != 0) {
                // 如果越界就从奇数位开始
                if(i >= len) {
                    i = 1;
                }
                // 填入
                ret[i] = k;
                hash[k]--;
                i += 2;
            }
        }


        return ret;

    }
}

/**
 * 贪心_填表+贪心:重构字符串
 */

class Solution3 {
    public String reorganizeString(String s) {
        int len = s.length();
        // 准备工作
        char[] hash = new char[26];
        char[] ret = new char[len];
        char maxValue = 'a';
        int maxCount = 0;

        // 统计个数并得到最大数量的字符
        for(int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            hash[ch-'a']++;
            // 最大数量
            if(hash[ch-'a'] > maxCount) {
                maxCount = hash[ch-'a'];
                maxValue = ch;
            }
        }

        // 这里判断是否能够重构字符串
        if(maxCount > (len + 1) / 2) {
            return "";
        }

        int index = 0;
        // 把最多数量的字符进行填表
        while(hash[maxValue - 'a'] != 0) {
            // if(index >= len) {
            //     return "";
            // }
            ret[index] = maxValue;
            hash[maxValue - 'a']--;
            index += 2;
        }

        // 然后把其他进行填表
        for(int i = 0 ; i < 26; i++) {
            char ch = (char)(i + 'a');
            while(hash[i]  != 0) {
                if(index >= len) {
                    index = 1;
                }
                ret[index] = ch;
                index += 2;
                hash[i]--;
            }
        }

        return new String(ret);
    }
}